Query evaluation.page (1125B)
1 The task of **query evaluation** is concerned with the complexity of determining whether a database satisfies a logical formula. In other words, it is the analogue of the logical problem of [model checking](). 2 3 # Complexity measures 4 5 TODO: combined complexity, data complexity, query complexity 6 7 # Basic results 8 9 TODO 10 11 # Non-Boolean queries 12 13 It is often most convenient to assume that queries are Boolean, so query evaluation returns a YES/NO answer. If a query $Q(\mathbf{x})$ is non-Boolean, we can always reduce to the Boolean case by considering all possible results of the query, i.e., all tuples $\mathbf{a}$ of the active domain of the database instance, and solving query evaluation for each of the Boolean queries $Q(\mathbf{a})$. Note that this reduction is in [PTIME](Complexity classes) if the arity of the query is fixed. 14 15 A different perspective on non-Boolean queries is to write the query in [relational algebra]() and consider the evaluation of relational algebra instead. 16 17 Yet another perspective is to study the complexity of producing the query results in succession: see [Enumeration of query results]().